#include<iostream>
#include<assert.h>
#include<vector>
#include<stack>
using namespace std;
struct BTNode
{
	int data;
	struct BTNode* left;
	struct BTNode* right;
};
BTNode* CreateTree()
{
	BTNode* n1 = new BTNode;
	BTNode* n2 = new BTNode;
	BTNode* n3 = new BTNode;
	BTNode* n4 = new BTNode;
	BTNode* n5 = new BTNode;
	BTNode* n6 = new BTNode;

	n1->data = 1;
	n2->data = 2;
	n3->data = 3;
	n4->data = 4;
	n5->data = 5;
	n6->data = 6;


	n1->left = n2;
	n1->right = n3;
	n2->left = n4;
	n2->right = n5;
	n4->left = nullptr;
	n4->right = nullptr;
	n3->left = n6;
	n3->right = nullptr;
	n5->left = nullptr;
	n5->right = nullptr;
	n6->left = nullptr;
	n6->right = nullptr;

	return n1;
}
void preorderTraversal(BTNode* root)
{
	stack<BTNode*>st;
	vector<int>result;
	if (root == nullptr)
	{
		return;
	}
	st.push(root);
	while (!st.empty())
	{
		BTNode* node = st.top();
		st.pop();
		result.push_back(node->data);
		if (node->right)
		{
			st.push(node->right);
		}
		if (node->left)
		{
			st.push(node->left);
		}
	}
	for (auto i = result.begin(); i != result.end(); i++)
	{
		cout << *i << " ";
	}
}
void inorderTraversal(BTNode* root)
{
	vector<int>result;

}
int main()
{
	BTNode* root=CreateTree();
	preorderTraversal(root);
	return 0;
}